UVa/321 - The New Villa/321.cpp

   1 /*
   2   Accepted
   3  */
   4 #include <iostream>
   5 #include <cassert>
   6 #include <queue>
   7 #include <vector>
   8 #include <algorithm>
   9
  10 using namespace std;
  11
  12 struct state{
  13   int i, lights, w;
  14   state() {}
  15   state(int I, int L, int W) : i(I), lights(L), w(W) {}
  16 };
  17
  18 const int MAXR = 10;
  19
  20 int toggleBit(int x, int b){
  21   if (x & (1 << b))
  22     return x & ~(1 << b);
  23   else
  24     return x | (1 << b);
  25 }
  26
  27 int differentBit(int x, int y){
  28   return __builtin_ctz(x ^ y);
  29 }
  30
  31 int main(){
  32   int r, d, s, C = 1;
  33   while (scanf("%d%d%d", &r, &d, &s) == 3 && (r+d+s)){
  34     vector<int> doors[r], switches[r];
  35     printf("Villa #%d\n", C++);
  36
  37     for (int i=0; i<d; ++i){
  38       int u, v;
  39       scanf("%d%d", &u, &v);
  40       --u, --v;
  41       doors[u].push_back(v);
  42       doors[v].push_back(u);
  43     }
  44
  45     for (int i=0; i<s; ++i){
  46       int u, v;
  47       scanf("%d%d", &u, &v);
  48       --u, --v;
  49       switches[u].push_back(v);
  50     }
  51
  52     bool visited[(1<<MAXR)+1][MAXR] = {false};
  53     state p[(1<<MAXR)+1][MAXR];
  54     for (int i=0; i<=(1<<MAXR); ++i){
  55       for (int j=0; j<MAXR; ++j){
  56         p[i][j] = state(-1, -1, -1);
  57       }
  58     }
  59
  60     queue<state> q;
  61     int length = -1;
  62     q.push(state(0, 1<<0, 0));
  63     while (q.size()){
  64       state u = q.front();
  65       //printf("popped state: i = %d, lights = %X, w = %d\n", u.i, u.lights, u.w);
  66       q.pop();
  67       if (u.i == r - 1 && u.lights == (1 << (r-1))){
  68         //Solution found
  69         //printf("Solution found. i = %d, lights = %X, w = %d\n", u.i, u.lights, u.w);
  70         length = u.w;
  71         break;
  72       }
  73
  74       if (visited[u.lights][u.i]) continue;
  75       visited[u.lights][u.i] = true;
  76
  77       vector<int> &s = switches[u.i];
  78       for (int j=0; j<s.size(); ++j){
  79         int nlights = toggleBit(u.lights, s[j]);
  80         if (!visited[nlights][u.i] && (nlights & (1 << u.i))){
  81           q.push(state(u.i, nlights, u.w + 1));
  82           if (p[nlights][u.i].i == -1) p[nlights][u.i] = u;
  83           //printf("  pushed state: i = %d, lights = %X, w = %d\n", u.i, nlights, u.w + 1);
  84         }
  85       }
  86
  87       vector<int> &d = doors[u.i];
  88       for (int j=0; j<d.size(); ++j){ //Moverme sin apagar luces
  89         if (!visited[u.lights][d[j]] && (u.lights & (1 << d[j]))){
  90           q.push(state(d[j], u.lights, u.w + 1));
  91           if (p[u.lights][d[j]].i == -1) p[u.lights][d[j]] = u;
  92           //printf("  pushed state: i = %d, lights = %X, w = %d\n", d[j], u.lights, u.w + 1);
  93         }
  94       }
  95     }
  96     if (length == -1){
  97       printf("The problem cannot be solved.\n");
  98     }else{
  99       printf("The problem can be solved in %d steps:\n", length);
 100       vector<state> w;
 101       state u = state(r-1, 1<<(r-1), -1);
 102       while (p[u.lights][u.i].i != -1){
 103         w.insert(w.begin(), u);
 104         u = p[u.lights][u.i];
 105       }
 106       w.insert(w.begin(), u);
 107       /*
 108       for (int i=0; i<w.size(); ++i){
 109         printf(" state: i = %d, lights = %X, w = %d\n", w[i].i, w[i].lights, w[i].w);
 110         }*/
 111       fprintf(stderr, "w.size() = %d, length = %d\n", w.size(), length);
 112       assert(w.size() == length+1);
 113       for (int i=1; i<w.size(); ++i){
 114         if (w[i].i != w[i-1].i){
 115           printf("- Move to room %d.\n", w[i].i + 1);
 116         }else{
 117           printf("- Switch %s light in room %d.\n", (w[i-1].lights < w[i].lights ? "on" : "off"), differentBit(w[i-1].lights, w[i].lights) + 1);
 118         }
 119       }
 120     }
 121     printf("\n");
 122   }
 123   return 0;
 124 }